package com.fuang.sort;

/**
 * Created by Fuang on 2017-10-13.
 * 排序算法
 */
public class BaseSortAlgorithms {

    /**
     * 插入排序算法
     * 基本思想：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，
     *          直至整个序列有序为止。
     * 分类 ------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
     * 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 稳定
     * @param a
     * @return
     */
    public static int[] insertSort(int a[]) {
        if (a.length <= 1) {
            return a;
        }

        for (int i = 1; i < a.length; i++)         // 类似抓扑克牌排序
        {
            int curr = a[i];                 // 右手抓到一张扑克牌
            int j = i - 1;                  // 拿在左手上的牌总是排序好的
            while (j >= 0 && a[j] > curr)    // 将抓到的牌与手牌从右向左进行比较
            {
                a[j + 1] = a[j];            // 如果该手牌比抓到的牌大，就将其右移
                j--;
            }
            a[j + 1] = curr; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
        }

        return a;
    }

    /**
     * 选择排序算法
     * 基本思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，
     *          直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(n^2)
     * 最优时间复杂度 ---- O(n^2)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 不稳定
     * @param a
     * @return
     */
    public static int[] selectSort(int a[]) {
        if (a.length <= 1) {
            return a;
        }

        for (int i = 0; i < a.length - 1; i++) {
            int min = a[i];
            int k = i;
            // 循环查找最小值和最小值所在的位置
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    k = j;
                }
            }

            if (min != a[i]) { // 若第一个元素非最小值，则与最小值兑换位置
                a[k] = a[i];
                a[i] = min;
            }
        }

        return a;
    }

    /**
     * 冒泡排序
     * 基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
     *          即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(n^2)
     * 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 稳定
     * @param a
     * @return
     */
    public static int[] bubbleSort(int a[]) {
        if (a.length <= 1) {
            return a;
        }

        int tmp;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    tmp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = tmp;
                }
            }
        }

        return a;
    }

    /**
     * 希尔排序
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
     * 最优时间复杂度 ---- O(n)
     * 平均时间复杂度 ---- 根据步长序列的不同而不同。
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 不稳定
     * @param a
     * @return
     */
    public static int[] shellSort(int a[]) {
        int h = 0;
        while (h <= a.length)                          // 生成初始增量
        {
            h = 3 * h + 1;
        }
        while (h >= 1)
        {
            for (int i = h; i < a.length; i++)
            {
                int j = i - h;
                int get = a[i];
                while (j >= 0 && a[j] > get)
                {
                    a[j + h] = a[j];
                    j = j - h;
                }
                a[j + h] = get;
            }
            h = (h - 1) / 3;                    // 递减增量
        }

        return a;
    }

    public static void main(String[] args) {
        int a[] = {4,5,7,3,1,7,6,8,9,2,0};
        print(insertSort(a));
        a = new int[]{4,5,7,3,1,7,6,8,9,2,0};
        print(selectSort(a));
        a = new int[]{4,5,7,3,1,7,6,8,9,2,0};
        print(bubbleSort(a));
        a = new int[]{4,5,7,3,1,7,6,8,9,2,0};
        print(shellSort(a));
    }

    private static void print(int a[]) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }

        System.out.print("\n");
    }
}
